package org.nowcoder.leetcode.sort;

import java.util.Arrays;

/**
 * Title  : 75. Sort Colors
 * Source : https://leetcode.cn/problems/sort-colors/
 * Author : XrazYang
 * Date   : 2023-05-31
 */

public class LeetCode_75 {
    public void sortColors(int[] nums) {
        //第一种：暴力解，无解时就是最优解
        //Arrays.sort(nums);

        //第二种：计数排序
//        int[] count = new int[]{0, 0, 0};
//        for (int i = 0; i < nums.length; i++) {
//            count[nums[i]] += 1;
//        }
//
//        int index = 0;
//        for (int i = 0; i < 3; i++) {
//            for (int j = 0; j < count[i]; j++) {
//                nums[index++] = i;
//            }
//        }
        //第三种：三路快排序partition
        //1. 定义好设置变量的含义
        int zero = -1; //[0,zero] 1
        int two = nums.length; // [two,nums.length-1] 2
        for (int i = 0; i < two; ) {
            if (nums[i] == 1) {
                i++;
            } else if (nums[i] == 2) {
                nums[i] = nums[--two];
                nums[two] = 2;
            } else {
                assert nums[i] == 0;
                nums[i++] = nums[++zero];
                nums[zero] = 0;
            }
        }
        System.out.println(Arrays.toString(nums));
    }
}
